#include <stdio.h>
#include <stdlib.h>
#define LH +1
#define EH  0
#define RH -1
typedef int ElemType;
typedef enum {false,true} bool;

typedef struct BSTNode{
    ElemType data;
    int bf;//balance flag
    struct BSTNode *lchild,*rchild;
}*BSTree,BSTNode;


BSTree RR_Rotate(BSTree p)
{
    // 右旋 A ↘ B ↘ C  =>  A ↙ B ↘ C
    BSTree lc = p->lchild;
    p->lchild = lc->rchild;
    lc->rchild = p;
    p = lc;
    return p;
}

BSTree LL_Rotate(BSTree p)
{
    // 左旋 A ↙ B ↙ C  =>  A ↙ B ↘ C
    BSTree rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
    return p;
}

BSTree LR_Rotate(BSTree p)
{
    p->lchild = LL_Rotate(p->lchild);
    return RR_Rotate(p);
}

BSTree RL_Rotate(BSTree p)
{
    p->rchild = RR_Rotate(p->rchild);
    return LL_Rotate(p);
}

void insertNode(BSTree tree,ElemType data){
    
}

int main(int argc, char const *argv[])
{
    /* code */
    return 0;
}